package com.cb2.algorithm.leetcode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * <a href="https://leetcode.cn/problems/add-one-row-to-tree/">在二叉树中增加一行(Add One Row to Tree)</a>
 * <p>给定一个二叉树的根 root 和两个整数 val 和 depth ，在给定的深度 depth 处添加一个值为 val 的节点行。</p>
 * <p>注意，根节点 root 位于深度 1 。</p>
 * <p>加法规则如下:
 * <ul>
 *     <li>给定整数 depth，对于深度为 depth - 1 的每个非空树节点 cur ，创建两个值为 val 的树节点作为 cur 的左子树根和右子树根。</li>
 *     <li>cur 原来的左子树应该是新的左子树根的左子树。</li>
 *     <li>cur 原来的右子树应该是新的右子树根的右子树。</li>
 *     <li>如果 depth == 1 意味着 depth - 1 根本没有深度，那么创建一个树节点，值 val 作为整个原始树的新根，而原始树就是新根的左子树。</li>
 * </ul>
 * </p>
 * <p>
 *     <b>示例：</b>
 * <pre>
 * 示例 1:
 *      输入: root = [4,2,6,3,1,5], val = 1, depth = 2
 *                   4                   4
 *                 /   \               /   \
 *                2     6  ==>        1     1
 *               / \   /             /       \
 *              3   1 5             2         6
 *                                 / \       /
 *                                3   1     5
 *      输出: [4,1,1,2,null,null,6,3,1,5]
 *
 * 示例 2:
 *      输入: root = [4,2,null,3,1], val = 1, depth = 3
 *                  4                   4
 *                /                    /
 *              2           ==>       2
 *             / \                   / \
 *            3   1                 1   1
 *                                 /     \
 *                                3       1
 *      输出:  [4,2,null,1,1,3,null,null,1]
 * </pre>
 * </p>
 * <p>
 * <b>提示:</b>
 * <ul>
 *     <li>节点数在 [1, 10^4] 范围内</li>
 *     <li>树的深度在 [1, 10^4]范围内</li>
 *     <li>-100 <= Node.val <= 100</li>
 *     <li>-10^5 <= val <= 10^5</li>
 *     <li>1 <= depth <= the depth of tree + 1</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/5/23 16:37
 */
public class LC0623AddOneRow_M {
    static class Solution {
        public TreeNode addOneRow(TreeNode root, int val, int depth) {
            // 如果 depth == 1 意味着 depth - 1 根本没有深度，那么创建一个树节点，值 val 作为整个原始树的新根，而原始树就是新根的左子树。
            if (depth == 1) {
                return new TreeNode(val, root, null);
            }
            //iteration(root, val, depth);
            dfs(root, val, depth, 1);
            return root;
        }

        private void iteration(TreeNode root, int val, int depth) {
            // 层序遍历
            int currDepth = 1;
            Queue<TreeNode> helper = new LinkedList<>();
            helper.offer(root);
            while (!helper.isEmpty()) {
                int currLevelNodeSize = helper.size();
                // 需要添加新行
                if (currDepth + 1 == depth) {
                    for (int i = 0; i < currLevelNodeSize; i++) {
                        TreeNode currNode = helper.poll();
                        currNode.left = new TreeNode(val, currNode.left, null);
                        currNode.right = new TreeNode(val, null, currNode.right);
                    }
                    break;
                } else {
                    for (int i = 0; i < currLevelNodeSize; i++) {
                        TreeNode currNode = helper.poll();
                        if (currNode.left != null) {
                            helper.offer(currNode.left);
                        }
                        if (currNode.right != null) {
                            helper.offer(currNode.right);
                        }
                    }
                }
                ++currDepth;
            }
        }

        public void dfs(TreeNode currNode, int val, int depth, int currDepth) {
            if (currNode == null) {
                return;
            }
            if (currDepth + 1 == depth) {

                currNode.left = new TreeNode(val, currNode.left, null);
                currNode.right = new TreeNode(val, null, currNode.right);
                return;
            }
            dfs(currNode.left, val, depth, currDepth + 1);
            dfs(currNode.right, val, depth, currDepth + 1);
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        Printer.printTreeNode(solution.addOneRow(Generator.buildTree(4, 2, 6, 3, 1, 5), 1, 2));
        Printer.printTreeNode(solution.addOneRow(Generator.buildTree(4, 2, null, 3, 1), 1, 3));
        Printer.printTreeNode(solution.addOneRow(Generator.buildTree(1, 2, 3, 4), 5, 4));
        Printer.printTreeNode(solution.addOneRow(Generator.buildTree(1, 2, 3, 4,1,5), 5, 4));
    }
}